{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Min Cost Climbing Stairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCostClimbingStairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使用最小花费爬楼梯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>cost</code> ，其中 <code>cost[i]</code> 是从楼梯第 <code>i</code> 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。</p>\n",
    "\n",
    "<p>你可以选择从下标为 <code>0</code> 或下标为 <code>1</code> 的台阶开始爬楼梯。</p>\n",
    "\n",
    "<p>请你计算并返回达到楼梯顶部的最低花费。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [10,<em><strong>15</strong></em>,20]\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>你将从下标为 1 的台阶开始。\n",
    "- 支付 15 ，向上爬两个台阶，到达楼梯顶部。\n",
    "总花费为 15 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [<em><strong>1</strong></em>,100,<em><strong>1</strong></em>,1,<em><strong>1</strong></em>,100,<em><strong>1</strong></em>,<em><strong>1</strong></em>,100,<em><strong>1</strong></em>]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>你将从下标为 0 的台阶开始。\n",
    "- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。\n",
    "- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。\n",
    "- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。\n",
    "- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。\n",
    "- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。\n",
    "- 支付 1 ，向上爬一个台阶，到达楼梯顶部。\n",
    "总花费为 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= cost.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= cost[i] &lt;= 999</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [min-cost-climbing-stairs](https://leetcode.cn/problems/min-cost-climbing-stairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [min-cost-climbing-stairs](https://leetcode.cn/problems/min-cost-climbing-stairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,15,20]', '[1,100,1,1,1,100,1,1,100,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        #dp[i] = min(dp[i-1], dp[i-2])\n",
    "        rst = {0:0,1:0}\n",
    "        \n",
    "        def subMinCostClimbingStairs(level):\n",
    "            if level == 0 or level == 1:\n",
    "                return 0\n",
    "            if level in rst:\n",
    "                return rst[level]\n",
    "\n",
    "            curr_cost = min(subMinCostClimbingStairs(level - 1) + cost[level - 1], subMinCostClimbingStairs(level - 2) + cost[level - 2])\n",
    "            rst[level] = curr_cost\n",
    "            return curr_cost\n",
    "        \n",
    "        return subMinCostClimbingStairs(len(cost))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = cost[:2]\n",
    "        for i in range(2, len(cost)):\n",
    "            dp.append(cost[i] + min(dp[-1], dp[-2]))\n",
    "        return min(dp[-1], dp[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = {0: cost[0], 1:cost[1]}\n",
    "        len_cost = len(cost)\n",
    "        \n",
    "        for i in range(2,len_cost):\n",
    "            dp[i] = min(dp[i-2]+cost[i],dp[i-1]+cost[i])\n",
    "        \n",
    "        print(dp)\n",
    "        return min(dp[len_cost-1],dp[len_cost-2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # n = len(cost)\n",
    "        # if n == 1:\n",
    "        #     return cost[0]\n",
    "        # if n == 2:\n",
    "        #     return min(cost[0],cost[1])\n",
    "        # costs = [0,0]\n",
    "        # for i in range(2,n+1):\n",
    "        #     costs.append(min(costs[i-1]+cost[i-1],costs[i-2] + cost[i-2]))\n",
    "        # return costs[-1]\n",
    "    \n",
    "    \n",
    "    \n",
    "        l1,l2=cost[0],cost[1]\n",
    "        for i in range(2,len(cost)):\n",
    "            tmp = l2\n",
    "            l2 = min(l1,l2) + cost[i]\n",
    "            l1 = tmp\n",
    "        return min(l1,l2) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # c(n) = min(c[n-1], c[n-2])+cost[n]\n",
    "        first = cost[0]\n",
    "        second = cost[1]\n",
    "        result = 0\n",
    "        cost.append(0)\n",
    "        for value in cost[2:]:\n",
    "            result = min(first, second)+value\n",
    "            first = second\n",
    "            second = result\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        p1,p2 = 0, 0\n",
    "        for i in range(2, len(cost)+1):\n",
    "            p1,p2 =p2, min(p2 + cost[i-1], p1 + cost[i-2])\n",
    "        return p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [0]*len(cost)\n",
    "        dp[0] = cost[1]\n",
    "        dp[1] = cost[2]\n",
    "        \n",
    "        for i in range(len(cost)):\n",
    "            dp[i] = cost[i] + min(dp[i-1],dp[i-2])\n",
    "        \n",
    "        return min(dp[len(cost)-1],dp[len(cost)-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self, nums, idx):\n",
    "        if idx >= len(nums):\n",
    "            return 0\n",
    "        if idx in self.mem:\n",
    "            return self.mem[idx]\n",
    "        self.mem[idx] = nums[idx] + min(self.helper(nums, idx+1), self.helper(nums, idx+2))\n",
    "        return self.mem[idx]\n",
    "    \n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        self.mem = {}\n",
    "        a = self.helper(cost, 0)\n",
    "        b = self.helper(cost, 1)\n",
    "        return min(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: 'List[int]') -> 'int':\n",
    "        dp = [[0,0] for _ in range(0,len(cost))]\n",
    "        dp[0][0] = cost[0]\n",
    "        dp[1][0] = cost[0]\n",
    "        dp[1][1] = cost[1]\n",
    "        for n in range(2, len(cost)):\n",
    "            print(n, n-1, n-2)\n",
    "            dp[n][0] = min(dp[n-1][0] + cost[n], dp[n-1][1] + cost[n], dp[n-2][0] + cost[n-1], dp[n-2][1] + cost[n-1])\n",
    "            dp[n][1] = min(dp[n-1][1] + cost[n-1],dp[n-1][0] + cost[n], dp[n-2][1] + cost[n-1], dp[n-2][0] + cost[n-1])\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(cost)\n",
    "        path = [-1 for i in range(m)]\n",
    "        \n",
    "        def f(i):\n",
    "            if i == m-1:\n",
    "                path[i] = cost[i]\n",
    "                return\n",
    "            elif i == m-2:\n",
    "                path[i] = cost[i] \n",
    "                return\n",
    "            else:\n",
    "                if path[i+1] ==-1:\n",
    "                    f(i+1)\n",
    "                if path[i+2] ==-1:\n",
    "                    f(i+2)\n",
    "                if path[i+1] < path[i+2]:\n",
    "                    path[i] = cost[i] +path[i+1]\n",
    "                else:\n",
    "                    path[i] = cost[i] +path[i+2]\n",
    "        f(0)\n",
    "        if path[0]<path[1]:\n",
    "            return path[0]\n",
    "        return path[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        f1 = f2 = 0\n",
    "        for x in reversed(cost):\n",
    "            f1, f2 = x + min(f1, f2), f1\n",
    "        return min(f1, f2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        length=len(cost)\n",
    "        if length==2:\n",
    "            return min(cost)\n",
    "        elif length==3:\n",
    "            return min(cost[1],cost[0]+cost[2])\n",
    "        cost1=min(cost[0],cost[1])\n",
    "        cost2=min(cost[1],cost[0]+cost[2])\n",
    "        for i in range(3,length):\n",
    "            tmp=cost2\n",
    "            cost2=min(cost2+cost[i],cost1+cost[i-1])\n",
    "            cost1=tmp\n",
    "        return cost2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=cost[0]\n",
    "        dp[1]=cost[1]\n",
    "        cost.append(0)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=min(dp[i-1],dp[i-2])+cost[i]\n",
    "            \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        res = [0]*len(cost)\n",
    "        res[0] = cost[0]\n",
    "        res[1] = cost[1]\n",
    "        for i in range(2,len(cost)):\n",
    "            res[i] = min(res[i-1],res[i-2])+cost[i]\n",
    "        return min(res[-1],res[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        f0, f1 = 0, 0\n",
    "        n = len(cost)\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            f0, f1 = f1, min(f0 + cost[i - 2], f1 + cost[i - 1])\n",
    "        \n",
    "        return f1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        a,b = cost[0],cost[1]\n",
    "        for i in range(2,len(cost)):\n",
    "            a,b = b,cost[i]+min(a,b)\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        for i in range(2,len(cost)):\n",
    "            cost[i]=min(cost[i-1],cost[i-2])+cost[i]\n",
    "        return min(cost[-2],cost[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        pre=[0,cost[0]]\n",
    "        # cost=cost+[0]\n",
    "        for i in range(1,len(cost)):\n",
    "            pre=[pre[1],min(pre[0]+cost[i],pre[1]+cost[i])]\n",
    "        return min(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "    #如果只有一个阶梯,\n",
    "    #那么最小值是 dp1= 0  \n",
    "    #如果有两个阶梯，最小值dp2 是 min(cos[0],cost[1])\n",
    "    #如果有三个阶梯。 最小值dp3就是min(cos[0]+cos[1],cos[0]+cos[2],cos[1])\n",
    "    #如果四个阶梯 最小值dp 4就是 min(dp[3])\n",
    "\n",
    "\n",
    "    #dp到达某个阶梯的最小花费。\n",
    "    #dp[0]=0,dp[1]=cost[0]\n",
    "    #dp[2] = cost[1]\n",
    "    #dp[3] = min(dp[2]+cost[2],dp[1]+cost[2])\n",
    "    #dp[4] = min(dp[3]+cost[3],dp[2]+cost[3])\n",
    "    #最红返回 min(dp[n],dp[n-1])\n",
    "        dp = [0 for i in range(len(cost)+1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] =cost[0] \n",
    "        dp[2] =cost[1]\n",
    "        if len(cost)==2:\n",
    "            return min(cost[0],cost[1])\n",
    "        for  i in range(3,len(cost)+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-1])\n",
    "            print(dp[i])\n",
    "        return min(dp[i],dp[i-1]) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.arrmv=[]\n",
    "        self.dp=[]\n",
    "    def dfs(self,n):\n",
    "\n",
    "        dp=self.dp\n",
    "        arrmv=self.arrmv\n",
    "        dfs=self.dfs\n",
    "        if n>=len(arrmv):return 0\n",
    "        if dp[n]!=-1:return dp[n]\n",
    "        dp[n]=min(dfs(n+1)+arrmv[n],dfs(n+2)+arrmv[n])\n",
    "        return dp[n]\n",
    "\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        self.dp=[-1]*n\n",
    "        self.arrmv=cost\n",
    "        dfs=self.dfs\n",
    "        return min(dfs(0),dfs(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dicts2 = {}\n",
    "\n",
    "    def step(self, cost: List[int], index: int) -> int:\n",
    "        #print(cost, index)\n",
    "       \n",
    "        if index < 0:\n",
    "            return 0\n",
    "\n",
    "        if index == 0:\n",
    "            self.dicts2[index] = 0\n",
    "\n",
    "        if index == 1:\n",
    "            self.dicts2[index] = 0\n",
    "\n",
    "        \n",
    "        if index in self.dicts2:\n",
    "            return self.dicts2[index]\n",
    "\n",
    "\n",
    "        #print(cost, index)\n",
    "        self.dicts2[index] = min(self.step(cost, index - 1) + cost[index - 1], self.step(cost, index - 2) + cost[index - 2] )\n",
    "        #print(self.dicts)\n",
    "\n",
    "        return self.dicts2[index]\n",
    "\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        self.dicts2 = {}\n",
    "        #print(cost, 0, self.dicts2)\n",
    "        return self.step(cost, len(cost))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        dp = [0]*(len(cost)+1)\n",
    "\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i] =min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0 for j in range(len(cost) + 1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range(2, len(cost) + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\r\n",
    "        cost.append(0)\r\n",
    "        n = len(cost)\r\n",
    "        dp = [0]*(n+1)\r\n",
    "        dp[0] = 0\r\n",
    "        dp[1] = cost[0]\r\n",
    "        dp[2] = cost[1]\r\n",
    "        for i in range(2, n+1):\r\n",
    "            dp[i] = min(dp[i-1], dp[i-2])+cost[i-1]\r\n",
    "            print('{}: {}'.format(i, dp[i]))\r\n",
    "        return dp[-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        @cache\n",
    "        def back(cur):\n",
    "            if n-cur <= 2:return cost[cur]\n",
    "            return cost[cur]+min(back(cur+1),back(cur+2))\n",
    "        #return min(back(0),back(1))\n",
    "        dp = [0]*(n+10)\n",
    "        dp[n-1],dp[n-2] = cost[n-1],cost[n-2]\n",
    "        for i in range(n-3,-1,-1):\n",
    "            dp[i] = cost[i]+min(dp[i+1],dp[i+2])\n",
    "        return min(dp[0],dp[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        length = len(cost)\n",
    "        dp = [0] * length\n",
    "        dp[-1] = cost[-1]\n",
    "        dp[-2] = cost[-2]\n",
    "        for i in range(length-3, -1, -1):\n",
    "            dp[i] = min(dp[i+1], dp[i+2]) + cost[i]\n",
    "        return min(dp[0], dp[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        size = len(cost)\n",
    "        dp = [0 for i in range(size+2)]\n",
    "        for i in range(2,size+1):\n",
    "            dp[i] =min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) \n",
    "        return dp[size]\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
